package book; // 6.2.2 单词基因变化 -> LC127

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class WordGeneSolution {
    // 返回两个单词是否基因变化（即刚好只有一个字母不同）
    boolean isGeneChange(String s1, String s2) {
        // n: 单词长度，根据题意s1和s2长度相等
        // d: 不同的字母个数，只有d==1才会返回true
        int n = s1.length(), d = 0;
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                d++;
                if (d > 1)
                    return false;
            }
        }
        return d == 1;
    }

    // 计算单词基因转换序列的长度
    public int wordGeneLength(String beginWord, String endWord, String[] wordList) {
        // 用字典表保存每个单词的最小演变次数
        // 除了beginWord其他单词初始化次数为-1
        Map<String, Integer> steps = new HashMap<>(wordList.length + 1);
        steps.put(beginWord, 0);
        for (String s : wordList)
            steps.put(s, -1);

        // 创建队列，保存状态为当前搜索的单词
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        // BFS - 基于队列开始搜索
        while (!queue.isEmpty()) {
            // 取出当前单词，记为s
            String s = queue.poll();
            // 从字典表取出当前长度，记为p
            int p = steps.get(s);
            // 搜索下一个可以演变的单词
            for (String t : wordList) {
                // 1. 判断是否新的目标点
                if (steps.get(t) == -1 && isGeneChange(s, t)) {
                    // 2. 判断是否已到达终点，是则直接返回
                    if (t.equals(endWord))
                        return p + 1;
                    // 3. 计算保存目标点状态
                    steps.put(t, p + 1);
                    // 4. 将目标点状态放入队列尾部
                    queue.offer(t);
                }
            }
        }

        // 没有结果返回-1
        return -1;
    }

    public static void main(String[] args) {
        String beginWord = "hit", endWord = "cog";
        String[] wordList = { "hot", "dot", "dog", "log", "cog" };
        int ans = new WordGeneSolution().wordGeneLength(beginWord, endWord, wordList);
        System.out.println("单词基因转换次数为: " + ans);
    }
}
